{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Adding Two Negabinary Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addNegabinary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #负二进制数相加"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出基数为 <strong>-2</strong>&nbsp;的两个数&nbsp;<code>arr1</code> 和&nbsp;<code>arr2</code>，返回两数相加的结果。</p>\n",
    "\n",
    "<p>数字以&nbsp;<em>数组形式</em><strong>&nbsp;</strong>给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，<code>arr&nbsp;= [1,1,0,1]</code>&nbsp;表示数字&nbsp;<code>(-2)^3&nbsp;+ (-2)^2 + (-2)^0 = -3</code>。<em>数组形式</em>&nbsp;中的数字 <code>arr</code> 也同样不含前导零：即&nbsp;<code>arr == [0]</code>&nbsp;或&nbsp;<code>arr[0] == 1</code>。</p>\n",
    "\n",
    "<p>返回相同表示形式的 <code>arr1</code> 和 <code>arr2</code> 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [1,1,1,1,1], arr2 = [1,0,1]\n",
    "<strong>输出：</strong>[1,0,0,0,0]\n",
    "<strong>解释：</strong>arr1 表示 11，arr2 表示 5，输出表示 16 。\n",
    "</pre>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [0], arr2 = [0]\n",
    "<strong>输出：</strong>[0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr1 = [0], arr2 = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr1.length,&nbsp;arr2.length &lt;= 1000</code></li>\n",
    "\t<li><code>arr1[i]</code>&nbsp;和&nbsp;<code>arr2[i]</code>&nbsp;都是&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code></li>\n",
    "\t<li><code>arr1</code>&nbsp;和&nbsp;<code>arr2</code>&nbsp;都没有前导0</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [adding-two-negabinary-numbers](https://leetcode.cn/problems/adding-two-negabinary-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [adding-two-negabinary-numbers](https://leetcode.cn/problems/adding-two-negabinary-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,1,1,1]\\n[1,0,1]', '[0]\\n[0]', '[0]\\n[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        carry = 0\n",
    "        res = []\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            if i >= 0:\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "            if x >= 2:\n",
    "                res.append(x - 2)\n",
    "                carry = -1\n",
    "            elif x == 1 or x == 0:\n",
    "                res.append(x)\n",
    "                carry = 0\n",
    "            else: # x = -1\n",
    "                res.append(1)\n",
    "                carry = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        while len(res) > 1 and res[-1] == 0:\n",
    "            res.pop()\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        carry = 0\n",
    "        result = []\n",
    "        for i in range(max(len(arr1), len(arr2)) + 2):\n",
    "            sum = 0\n",
    "            if i < len(arr1): sum += arr1[-i-1]\n",
    "            if i < len(arr2): sum += arr2[-i-1]\n",
    "            sum += carry\n",
    "            if sum == 0 or sum == 1: \n",
    "                carry = 0\n",
    "                result.append(sum)\n",
    "            elif sum == 2 or sum == 3: \n",
    "                result.append(sum - 2)\n",
    "                carry = -1\n",
    "            elif sum == -1: \n",
    "                result.append(1)\n",
    "                carry = 1\n",
    "        while len(result) > 1:\n",
    "            if result[-1] == 0:\n",
    "                result.pop()\n",
    "            else:\n",
    "                break\n",
    "        return result[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        # 计算两个数组的长度\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        # 初始化结果数组和进位\n",
    "        result = []\n",
    "        carry = 0\n",
    "\n",
    "        # 从最低有效位开始逐位相加\n",
    "        i, j = m - 1, n - 1\n",
    "        while i >= 0 or j >= 0 or carry != 0:\n",
    "            # 获取当前位的值\n",
    "            digit1 = arr1[i] if i >= 0 else 0\n",
    "            digit2 = arr2[j] if j >= 0 else 0\n",
    "\n",
    "            # 计算当前位的相加结果\n",
    "            curr_sum = digit1 + digit2 + carry\n",
    "            # 将当前位的值添加到结果数组中\n",
    "            result.append(curr_sum % 2)\n",
    "            # 计算进位\n",
    "            carry = -(curr_sum // 2)\n",
    "\n",
    "            # 移动到下一位\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "        # 去掉结果数组末尾的连续零\n",
    "        while len(result) > 1 and result[-1] == 0:\n",
    "            result.pop()\n",
    "\n",
    "        # 翻转结果数组，得到最终的结果\n",
    "        result.reverse()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i,j = len(arr1)-1,len(arr2)-1\n",
    "        c = 0\n",
    "        ans = []\n",
    "        while i>=0 or j>=0 or c:\n",
    "            a = 0 if i < 0 else arr1[i]\n",
    "            b = 0 if j < 0 else arr2[j]\n",
    "            x = a + b + c\n",
    "            c = 0\n",
    "            if x >= 2:\n",
    "                x = x-2\n",
    "                c = c-1\n",
    "            if x == -1:\n",
    "                x = 1\n",
    "                c += 1\n",
    "            ans.append(x)\n",
    "            i-=1\n",
    "            j-=1\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        # 计算两个数组的长度\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        # 初始化结果数组和进位\n",
    "        result = []\n",
    "        carry = 0\n",
    "\n",
    "        # 从最低有效位开始逐位相加\n",
    "        i, j = m - 1, n - 1\n",
    "        while i >= 0 or j >= 0 or carry != 0:\n",
    "            # 获取当前位的值\n",
    "            digit1 = arr1[i] if i >= 0 else 0\n",
    "            digit2 = arr2[j] if j >= 0 else 0\n",
    "\n",
    "            # 计算当前位的相加结果\n",
    "            curr_sum = digit1 + digit2 + carry\n",
    "            # 将当前位的值添加到结果数组中\n",
    "            result.append(curr_sum % 2)\n",
    "            # 计算进位\n",
    "            carry = -(curr_sum // 2)\n",
    "\n",
    "            # 移动到下一位\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "        # 去掉结果数组末尾的连续零\n",
    "        while len(result) > 1 and result[-1] == 0:\n",
    "            result.pop()\n",
    "\n",
    "        # 翻转结果数组，得到最终的结果\n",
    "        result.reverse()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j, carry, result = len(arr1) - 1, len(arr2) - 1, 0, []\n",
    "\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            if i >= 0:\n",
    "                carry += arr1[i]\n",
    "                i -= 1\n",
    "            if j >= 0:\n",
    "                carry += arr2[j]\n",
    "                j -= 1\n",
    "            result.append(carry & 1)\n",
    "            carry = -(carry >> 1)\n",
    "\n",
    "        # 移除结果中的前导零\n",
    "        while len(result) > 1 and result[-1] == 0:\n",
    "            result.pop()\n",
    "\n",
    "    # 反转结果以得到正确的顺序\n",
    "        result.reverse()\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def two_ten(a):\n",
    "            p = 0\n",
    "            ans = 0\n",
    "            for i in range(len(a) - 1, -1, -1):\n",
    "                ans += a[i] * (-2) ** p\n",
    "                p += 1\n",
    "            return ans\n",
    "\n",
    "        def ten_two(x):\n",
    "            if x == 0: return [0]\n",
    "            ans = []\n",
    "            while x:\n",
    "                ans.append(x & 1)\n",
    "                x >>= 1\n",
    "                x = -x\n",
    "            return ans[::-1]\n",
    "\n",
    "        return ten_two(two_ten(arr1) + two_ten(arr2))\n",
    "\n",
    "'''\n",
    "10000\n",
    "  000\n",
    "\n",
    "1 -2 \n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        m, n = len(arr1), len(arr2)\n",
    "        i, j = m-1, n-1\n",
    "        carry = 0\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            x += arr1[i] if i >= 0 else 0\n",
    "            x += arr2[j] if j >= 0 else 0\n",
    "            if x >= 2:\n",
    "                res.append(x-2)\n",
    "                carry = -1\n",
    "            elif x >= 0:\n",
    "                res.append(x)\n",
    "                carry = 0\n",
    "            else:\n",
    "                res.append(1)\n",
    "                carry = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        while len(res) > 1 and res[-1] == 0:\n",
    "            res.pop()\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "sys.set_int_max_str_digits(0)  # 大数的范围坑\n",
    "\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def get_k_bin_of_n(n, k):\n",
    "    # 整数n的k进制计算（支持正数进制与负数进制）二进制、三进制、十六进制、负进制\n",
    "    if n == 0:\n",
    "        return [0]\n",
    "    if k == 0:\n",
    "        return []\n",
    "    assert abs(k) >= 2  # 原则上要求\n",
    "    # 支持正负数\n",
    "    pos = 1 if k > 0 else -1\n",
    "    k = abs(k)\n",
    "    lst = []  # 0123456789\" + \"\".join(chr(i+ord(\"A\")) for i in range(26))\n",
    "    while n:\n",
    "        lst.append(n % k)\n",
    "        n //= k\n",
    "        n *= pos\n",
    "    lst.reverse()\n",
    "    # 最高支持三十六进制的表达\n",
    "    return lst\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        \n",
    "    \n",
    "        def check(tmp):\n",
    "            res = 0\n",
    "            for num in tmp:\n",
    "                res  = (-2)*res + num\n",
    "            return res\n",
    "        \n",
    "        ans = check(arr1) + check(arr2)\n",
    "        return get_k_bin_of_n(ans, -2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        carry = 0\n",
    "        ans = list()\n",
    "\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            if i >= 0:\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "\n",
    "            if x >= 2:\n",
    "                ans.append(x - 2)\n",
    "                carry = -1\n",
    "            elif x >= 0:\n",
    "                ans.append(x)\n",
    "                carry = 0\n",
    "            else:\n",
    "                ans.append(1)\n",
    "                carry = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        for i in arr1:\n",
    "            p1 = i-p1-p1\n",
    "        for i in arr2:\n",
    "            p2 = i-p2-p2\n",
    "        p = p1 + p2\n",
    "        if p == 0:return [0]\n",
    "        res = []\n",
    "        a = 1\n",
    "        while p != 0:\n",
    "            if p%2 == 0:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                p -= a\n",
    "                res.append(1)\n",
    "            a = -a \n",
    "            p = p // 2\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        if len(arr1) < len(arr2):\n",
    "            return self.addNegabinary(arr2, arr1)\n",
    "        \n",
    "        arr1.reverse()\n",
    "        arr2.reverse()\n",
    "\n",
    "        res = []\n",
    "        le =len(arr1)\n",
    "        carry = 0\n",
    "        for i in range(le + 2):\n",
    "            x2 = 0 if i > len(arr2)-1 else arr2[i]\n",
    "            x1 = 0 if i > len(arr1)-1 else arr1[i]\n",
    "            x = x1 + x2 + carry\n",
    "            if 0 <= x < 2:\n",
    "                res.append(x)\n",
    "                carry = 0\n",
    "            elif x >= 2:\n",
    "                res.append(x-2)\n",
    "                carry = -1\n",
    "            elif x == -1:\n",
    "                res.append(1)\n",
    "                carry = 1\n",
    "\n",
    "        while len(res) > 1 and res[-1] == 0:\n",
    "            res.pop()\n",
    "        return res[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j, c = len(arr1) - 1, len(arr2) - 1, 0\n",
    "        ans = []\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            a = arr1[i] if i >= 0 else 0\n",
    "            b = arr2[j] if j >= 0 else 0\n",
    "            x = a + b + c\n",
    "            if x >= 2:\n",
    "                x -= 2\n",
    "                c = -1\n",
    "            elif x == -1:\n",
    "                x = 1\n",
    "                c = 1\n",
    "            else:\n",
    "                c = 0\n",
    "\n",
    "            ans.append(x)\n",
    "            i, j = i - 1, j - 1\n",
    "        while len(ans) > 1 and not ans[-1]:\n",
    "            ans.pop()\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        if len(arr1) < len(arr2):\n",
    "            arr1, arr2 = arr2, arr1\n",
    "\n",
    "        arr1.reverse()\n",
    "        arr2.reverse()\n",
    "\n",
    "        for i in range(len(arr2)):\n",
    "            arr1[i] += arr2[i]\n",
    "\n",
    "        arr1.extend([0, 0, 0])\n",
    "        i = 0\n",
    "        while i < len(arr1):\n",
    "            if arr1[i] >= 2:\n",
    "                v = arr1[i] // 2\n",
    "                arr1[i] %= 2\n",
    "                arr1[i + 1] -= v\n",
    "            elif arr1[i] <= -1:\n",
    "                arr1[i] *= -1\n",
    "                arr1[i + 1] += arr1[i]\n",
    "            i += 1\n",
    "\n",
    "        while arr1 and arr1[-1] == 0:\n",
    "            arr1.pop()\n",
    "\n",
    "        arr1.reverse()\n",
    "\n",
    "        return arr1 if len(arr1) > 0 else [0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        c = 0\n",
    "        ans = []\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            a = 0 if i < 0 else arr1[i]\n",
    "            b = 0 if j < 0 else arr2[j]\n",
    "            x = a + b + c\n",
    "            c = 0\n",
    "            if x >= 2:\n",
    "                x -= 2\n",
    "                c -= 1\n",
    "            elif x == -1:\n",
    "                x = 1\n",
    "                c += 1\n",
    "            ans.append(x)\n",
    "            i, j = i - 1, j - 1\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        c = 0\n",
    "        ans = []\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            a = 0 if i < 0 else arr1[i]\n",
    "            b = 0 if j < 0 else arr2[j]\n",
    "            x = a + b + c\n",
    "            c = 0\n",
    "            if x >= 2:\n",
    "                x -= 2\n",
    "                c -= 1\n",
    "            elif x == -1:\n",
    "                x = 1\n",
    "                c += 1\n",
    "            ans.append(x)\n",
    "            i, j = i - 1, j - 1\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr1 = arr1[::-1]\n",
    "        arr2 = arr2[::-1]\n",
    "        arr = []\n",
    "        carry = 0\n",
    "        i = 0\n",
    "        while i < max(len(arr1), len(arr2)) or carry != 0:\n",
    "            temp = 0\n",
    "            temp += arr1[i] if i < len(arr1) else 0\n",
    "            temp += arr2[i] if i < len(arr2) else 0\n",
    "            temp += carry\n",
    "            arr.append(1 & temp)\n",
    "            carry = (temp - (1 & temp)) // (-2)\n",
    "            i += 1\n",
    "        arr = arr[::-1]\n",
    "        cor = len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] != 0:\n",
    "                cor = i\n",
    "                break\n",
    "        return [0] if cor == len(arr) else arr[cor:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1,len(arr2) - 1\n",
    "        c = 0\n",
    "        ans = []\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            a = 0 if i < 0 else arr1[i]\n",
    "            b = 0 if j < 0 else arr2[j]\n",
    "            x = a + b + c\n",
    "            c = 0\n",
    "            if x >= 2:\n",
    "                x -= 2\n",
    "                c -= 1\n",
    "            elif x== -1:\n",
    "                x = 1\n",
    "                c += 1\n",
    "            ans.append(x)\n",
    "            i,j = i-1, j-1\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def getNum(arr):\n",
    "            flag = 1\n",
    "            digit = 0\n",
    "            res = 0\n",
    "\n",
    "            for i in range(len(arr)-1, -1, -1):\n",
    "                if arr[i] == 1:    \n",
    "                    res += (1 << digit) * flag\n",
    "                \n",
    "                flag *= -1\n",
    "                digit += 1\n",
    "                \n",
    "\n",
    "            return res\n",
    "        \n",
    "        def decodeNum(num):\n",
    "            if num == 0:\n",
    "                return [0]\n",
    "                \n",
    "            r = []\n",
    "\n",
    "            while num != 0:\n",
    "                c = abs(num % -2)\n",
    "                r.append(c)\n",
    "                num = (num - c) // -2\n",
    "\n",
    "            return r[::-1]\n",
    "        \n",
    "        return decodeNum(getNum(arr1) + getNum(arr2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def two_ten(a):\n",
    "            p = 0\n",
    "            ans = 0\n",
    "            for i in range(len(a) - 1, -1, -1):\n",
    "                ans += a[i] * (-2) ** p\n",
    "                p += 1\n",
    "            return ans\n",
    "\n",
    "        def ten_two(x):\n",
    "            if x == 0: return [0]\n",
    "            ans = []\n",
    "            while x:\n",
    "                # ans.append(x & 1)\n",
    "                # x >>= 1\n",
    "                # x = -x\n",
    "                ans.append(abs(x % -2))\n",
    "                x = (x - abs(x % -2)) // -2\n",
    "            return ans[::-1]\n",
    "\n",
    "        return ten_two(two_ten(arr1) + two_ten(arr2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        num1 = 0\n",
    "        num2 = 0\n",
    "        for i, arr in enumerate(arr1[::-1]):\n",
    "            num1 += arr * (-2) ** i\n",
    "        for j, a in enumerate(arr2[::-1]):\n",
    "            num2 += a * (-2) ** j \n",
    "        num = num1 + num2\n",
    "        if num == 0:\n",
    "            return [0]\n",
    "        res = []\n",
    "        while num:\n",
    "            # remainder = n & 1\n",
    "            remainder = abs(num) % 2\n",
    "            res.append(remainder)\n",
    "            num -= remainder\n",
    "            num //= -2\n",
    "        return res[::-1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j  = len(arr1)-1, len(arr2)-1\n",
    "        c = 0\n",
    "        ans = []\n",
    "        while i >=0 or j >= 0 or c:\n",
    "            a = arr1[i] if i >=0 else 0\n",
    "            b = arr2[j] if j >=0 else 0\n",
    "            x = a+b+c \n",
    "            c = 0\n",
    "            if x >= 2:\n",
    "                x -= 2\n",
    "                c = -1\n",
    "            elif x == -1:\n",
    "                x = 1\n",
    "                c = 1\n",
    "            ans.append(x)\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        if len(arr1) < len(arr2):\n",
    "            arr1, arr2 = arr2, arr1\n",
    "        n2 = len(arr2)\n",
    "        for i in range(1, n2+1):\n",
    "            arr1[-i] += arr2[-i]\n",
    "        ans = [0, 0] + arr1\n",
    "        n1 = len(arr1) + 2\n",
    "        for i in range(n1-1, 1, -1):\n",
    "            if ans[i] >= 2:\n",
    "                ans[i] -= 2\n",
    "                if ans[i-1] >= 1:\n",
    "                    ans[i-1] -= 1\n",
    "                else:\n",
    "                    ans[i-1] += 1\n",
    "                    ans[i-2] += 1\n",
    "        i = 0\n",
    "        while i < n1 and ans[i] == 0:\n",
    "            i += 1\n",
    "        return ans[i:] if i < n1 else [0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "\n",
    "        s = 0\n",
    "        for i, c in enumerate(arr1[::-1]):\n",
    "            s += (-2) ** i * c\n",
    "        for i, c in enumerate(arr2[::-1]):\n",
    "            s += (-2) ** i * c\n",
    "        \n",
    "        ans = []\n",
    "        if s == 0:\n",
    "            return [0]\n",
    "        while s:\n",
    "            s, mod = s // -2, s % -2\n",
    "            if mod == -1:\n",
    "                s += 1\n",
    "                mod = 1\n",
    "            ans.append(mod)\n",
    "        return ans[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ans = deque([])\n",
    "        tmp1 = arr1 if len(arr1) > len(arr2) else arr2\n",
    "        tmp2 = arr1 if len(arr1) <= len(arr2) else arr2\n",
    "        c = 0\n",
    "        for i in range(len(tmp1)) :\n",
    "            t2 = 0\n",
    "            if i < len(tmp2) :\n",
    "                t2 = tmp2[-i-1]\n",
    "            a = tmp1[-i-1] + t2 + c\n",
    "            if a < 0 :\n",
    "                a = 1\n",
    "                c = 1\n",
    "            elif a >= 2 :\n",
    "                a -= 2\n",
    "                c = -1\n",
    "            else :\n",
    "                c = 0\n",
    "            ans.appendleft(a)\n",
    "        if c < 0:\n",
    "            ans.appendleft(1)\n",
    "            ans.appendleft(1)\n",
    "        elif c == 1:\n",
    "            ans.appendleft(1)\n",
    "        while len(ans) > 1 and ans[0] == 0:\n",
    "           ans.popleft()\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        n1 = len(arr1)\n",
    "        n2 = len(arr2)\n",
    "        res = []\n",
    "        start_idx = 1\n",
    "        cur = 0\n",
    "        while start_idx <= max(n1,n2):\n",
    "            if start_idx <= n1:\n",
    "                tmp1 = arr1[-start_idx]\n",
    "            else:\n",
    "                tmp1 = 0\n",
    "            if start_idx <= n2:\n",
    "                tmp2 = arr2[-start_idx]\n",
    "            else:\n",
    "                tmp2 = 0\n",
    "            tmp_sum = tmp1 + tmp2 + cur\n",
    "            #print( tmp1 , tmp2 , cur , res)\n",
    "            cur = -(tmp_sum // 2)\n",
    "            res.append( tmp_sum % 2 )\n",
    "            start_idx += 1\n",
    "        if cur == -1:  #判断最后是否还有未进位的\n",
    "            res.append(1)\n",
    "            res.append(1)\n",
    "        res.reverse()\n",
    "        idx_1 = res.index(1) if 1 in res else len(res) - 1\n",
    "        res = res[idx_1:]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i = len(arr1) - 1\n",
    "        j = len(arr2) - 1\n",
    "        c = 0\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            a = arr1[i] if i >= 0 else 0\n",
    "            b = arr2[j] if j >= 0 else 0\n",
    "            s = a + b + c\n",
    "            if s == -1:\n",
    "                ans.append(1)\n",
    "                c = 1\n",
    "            elif 0 <= s <= 1:\n",
    "                ans.append(s)\n",
    "                c = 0\n",
    "            elif s == 2:\n",
    "                ans.append(0)\n",
    "                c = -1\n",
    "            elif s == 3:\n",
    "                ans.append(1)\n",
    "                c = -1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "\n",
    "        k = len(ans) - 1\n",
    "        while k > 0:\n",
    "            if ans[k] == 0:\n",
    "                ans.pop()\n",
    "            else:\n",
    "                break\n",
    "            k -= 1\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        ans = []\n",
    "        c = 0\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            a = 0 if i < 0 else arr1[i]\n",
    "            b = 0 if j < 0 else arr2[j]\n",
    "            x = a + b + c\n",
    "            c = 0\n",
    "            if x >= 2:\n",
    "                x -= 2\n",
    "                c -= 1\n",
    "            elif x == -1:\n",
    "                x = 1\n",
    "                c += 1\n",
    "            ans.append(x)\n",
    "            i, j = i - 1, j - 1\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        ret = []\n",
    "        c = 0\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        while i >= 0 or j >= 0:\n",
    "            v1 = arr1[i] if i >= 0 else 0\n",
    "            v2 = arr2[j] if j >= 0 else 0\n",
    "            currv = v1 + v2 + c\n",
    "            r = currv % (-2)\n",
    "            c = currv // (-2)\n",
    "            if r < 0:\n",
    "                c += 1\n",
    "                r += 2\n",
    "            ret.append(r)\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        # print(ret, c)\n",
    "        while c:\n",
    "            r = c %(-2)\n",
    "            c = c // (-2)\n",
    "            if r < 0:\n",
    "                r += 2\n",
    "                c += 1\n",
    "            ret.append(r)\n",
    "        while ret and ret[-1] == 0:\n",
    "            ret.pop()\n",
    "\n",
    "        return ret[::-1] if ret else [0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i = len(arr1)-1\n",
    "        j = len(arr2)-1\n",
    "        k= 0\n",
    "        res = []\n",
    "        jinwei = 0\n",
    "        while i>=0 and j>=0:\n",
    "            num = arr1[i]+arr2[j] + jinwei\n",
    "            if num == 2:\n",
    "                jinwei = -1\n",
    "                num = 0\n",
    "            elif num == 3:\n",
    "                jinwei = -1\n",
    "                num = 1\n",
    "            elif num == -1:\n",
    "                jinwei = 1\n",
    "                num = 1\n",
    "            else:\n",
    "                jinwei = 0\n",
    "                num = num\n",
    "            res.append(num)\n",
    "            i-=1\n",
    "            j-=1\n",
    "        \n",
    "        \n",
    "        if i>=0:\n",
    "            while i>=0:\n",
    "                num = arr1[i] + jinwei\n",
    "                if num == 2:\n",
    "                    jinwei = -1\n",
    "                    num = 0\n",
    "                elif num == 3:\n",
    "                    jinwei = -1\n",
    "                    num = 1\n",
    "                elif num == -1:\n",
    "                    jinwei = 1\n",
    "                    num = 1\n",
    "                else:\n",
    "                    jinwei = 0\n",
    "                    num = num\n",
    "                res.append(num)\n",
    "                i-=1\n",
    "        \n",
    "        elif j>=0:\n",
    "            while j>=0:\n",
    "                num = arr2[j] + jinwei\n",
    "                if num == 2:\n",
    "                    jinwei = -1\n",
    "                    num = 0\n",
    "                elif num == 3:\n",
    "                    jinwei = -1\n",
    "                    num = 1\n",
    "                elif num == -1:\n",
    "                    jinwei = 1\n",
    "                    num = 1\n",
    "                else:\n",
    "                    jinwei = 0\n",
    "                    num = num\n",
    "                res.append(num)\n",
    "                j-=1\n",
    "     \n",
    "        if jinwei!=0:\n",
    "            if jinwei == -1:\n",
    "                res.append(1)\n",
    "                res.append(1)\n",
    "            elif jinwei == 1:\n",
    "                res.append(1)\n",
    "        while len(res)>=2 and res[-1]==0:\n",
    "            res.pop() \n",
    "        res.reverse()\n",
    "        return res\n",
    "                \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        # 进位\n",
    "        c = 0\n",
    "        ans = []\n",
    "\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            x = c\n",
    "            if i >= 0:\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "\n",
    "            # 根据和的情况进行处理\n",
    "            if x >= 2:\n",
    "                ans.append(x - 2)\n",
    "                c = -1\n",
    "            elif x >= 0:\n",
    "                ans.append(x)\n",
    "                c = 0\n",
    "            else:\n",
    "                ans.append(1)\n",
    "                c = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        \n",
    "        return ans[::-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        c = 0\n",
    "        ans = []\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            a = 0 if i < 0 else arr1[i]\n",
    "            b = 0 if j < 0 else arr2[j]\n",
    "            x = a + b + c\n",
    "            c = 0\n",
    "            if x >= 2:\n",
    "                x -= 2\n",
    "                c -= 1\n",
    "            elif x == -1:\n",
    "                x = 1\n",
    "                c += 1\n",
    "            ans.append(x)\n",
    "            i, j = i - 1, j - 1\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        for i in arr1:\n",
    "            p1 = i-p1-p1\n",
    "        for i in arr2:\n",
    "            p2 = i-p2-p2\n",
    "        p = p1 + p2\n",
    "        if p == 0:return [0]\n",
    "        res = []\n",
    "        a = 1\n",
    "        while p != 0:\n",
    "            if p%2 == 0:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                p -= a\n",
    "                res.append(1)\n",
    "            a = -a \n",
    "            p = p // 2\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        carry = 0\n",
    "        ans = list()\n",
    "\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            if i >= 0:\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "\n",
    "            if x >= 2:\n",
    "                ans.append(x - 2)\n",
    "                carry = -1\n",
    "            elif x >= 0:\n",
    "                ans.append(x)\n",
    "                carry = 0\n",
    "            else:\n",
    "                ans.append(1)\n",
    "                carry = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        carry = 0\n",
    "        ans = list()\n",
    "\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            if i >= 0:\n",
    "\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "\n",
    "            if x >= 2:\n",
    "                ans.append(x - 2)\n",
    "                carry = -1\n",
    "            elif x >= 0:\n",
    "                ans.append(x)\n",
    "                carry = 0\n",
    "            else:\n",
    "                ans.append(1)\n",
    "                carry = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        carry = 0\n",
    "        i = len(arr1)-1\n",
    "        j = len(arr2)-1\n",
    "        ans = []\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            if i >= 0:\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "            # 当前的数\n",
    "            if x >= 2:\n",
    "                ans.append(x-2)\n",
    "                carry = -1\n",
    "            elif x >= 0:\n",
    "                ans.append(x)\n",
    "                carry = 0\n",
    "            else:\n",
    "                ans.append(1)\n",
    "                carry = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        # 处理前导0\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr1 = arr1[::-1]\n",
    "        arr2 = arr2[::-1]\n",
    "        if len(arr1) > len(arr2):\n",
    "            arr = arr1\n",
    "            for i in range(len(arr2)):\n",
    "                arr[i] += arr2[i]\n",
    "        else:\n",
    "            arr = arr2\n",
    "            for i in range(len(arr1)):\n",
    "                arr[i] += arr1[i]\n",
    "        arr.append(0)\n",
    "        arr.append(0)\n",
    "        t = len(arr)\n",
    "        for j in range(t-1):\n",
    "            if arr[j] == 2:\n",
    "                arr[j] = 0\n",
    "                arr[j+1] += -1\n",
    "            elif arr[j] == -1:\n",
    "                arr[j] = 1\n",
    "                arr[j+1] += 1\n",
    "            elif arr[j] == 3:\n",
    "                arr[j] = 1\n",
    "                arr[j+1] += 1\n",
    "                arr[j+2] += 1\n",
    "            elif arr[j] == 4:\n",
    "                arr[j] = 0\n",
    "                arr[j+2] += 1\n",
    "        arr = arr[::-1]\n",
    "        for k in range(t-1):\n",
    "            if arr[0] == 1:\n",
    "                break\n",
    "            else:\n",
    "                arr.pop(0)\n",
    "        return arr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        # 进位\n",
    "        carry = 0\n",
    "        i = len(arr1)-1\n",
    "        j = len(arr2)-1\n",
    "        res = []\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            if i >= 0:\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "            # 判断当前位，然后进位多少\n",
    "            # x 有 -1，0，1，2，3\n",
    "            if x >= 2:\n",
    "                res.append(x-2)\n",
    "                carry = -1\n",
    "            elif x < 0:\n",
    "                res.append(1)\n",
    "                carry = 1\n",
    "            else:\n",
    "                res.append(x)\n",
    "                carry = 0\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        while len(res) > 1 and res[-1] == 0:\n",
    "            res.pop()\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "\n",
    "        # 模板：https://leetcode.cn/problems/convert-to-base-2/solutions/2210242/python3-duan-chu-fa-fu-er-jin-zhi-zhuan-1zahd/\n",
    "        # 将十进制的num转换为M进制 (注: 无法将负数num转换为正进制数)\n",
    "        def convert(num: int, M: int) -> List[int]:\n",
    "            if M == 0: return None\n",
    "            if num == 0: return [0]\n",
    "            x, y, res = num, 0, []\n",
    "            while x:\n",
    "                if M > 0:\n",
    "                    y = x % M\n",
    "                    x = x // M\n",
    "                else:\n",
    "                    y = x - (((x + M + 1) // M) * M)  # 余数\n",
    "                    x = (x + M + 1) // M               # 上取整\n",
    "                res.append(y)\n",
    "            return res[::-1]\n",
    "        \n",
    "        # 将任意进制M转换为十进制\n",
    "        def to10(num: List[int], M: int) -> int:\n",
    "            n = len(num)\n",
    "            return sum(num[j] * pow(M, i) for i, j in zip(range(n), range(n - 1, -1, -1)))\n",
    "\n",
    "        return convert(to10(arr1, -2) + to10(arr2, -2), -2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr1_index = len(arr1)-1\n",
    "        cur_1 = 0\n",
    "        for i in arr1:\n",
    "            cur_1+= pow(-2,arr1_index)*i\n",
    "            arr1_index-=1\n",
    "        arr2_index = len(arr2)-1\n",
    "        cur_2 = 0\n",
    "        for i in arr2:\n",
    "            cur_2+=pow(-2, arr2_index)*i\n",
    "            arr2_index-=1\n",
    "        cur_1+=cur_2\n",
    "        if cur_1 == 0:return [0]\n",
    "        res = self.to_negative_base(cur_1)\n",
    "        return res\n",
    "    def to_negative_base(self,decimal):\n",
    "        if decimal == 0:\n",
    "            return [0]\n",
    "        \n",
    "        digits = []\n",
    "        while decimal != 0:\n",
    "            remainder = abs(decimal) % 2\n",
    "            digits.insert(0, remainder)\n",
    "            decimal = (decimal - remainder) // -2\n",
    "        \n",
    "        return digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        def two_ten(a):\n",
    "            p = 0\n",
    "            ans = 0\n",
    "            for i in range(len(a) - 1, -1, -1):\n",
    "                ans += a[i] * (-2) ** p\n",
    "                p += 1\n",
    "            return ans\n",
    "\n",
    "        def ten_two(x):\n",
    "            if x == 0: return [0]\n",
    "            ans = []\n",
    "            while x:\n",
    "                ans.append(x & 1)\n",
    "                x >>= 1\n",
    "                x = -x\n",
    "            return ans[::-1]\n",
    "\n",
    "        return ten_two(two_ten(arr1) + two_ten(arr2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        carry = 0\n",
    "        ans = list()\n",
    "\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            if i >= 0:\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "\n",
    "            if x >= 2:\n",
    "                ans.append(x - 2)\n",
    "                carry = -1\n",
    "            elif x >= 0:\n",
    "                ans.append(x)\n",
    "                carry = 0\n",
    "            else:\n",
    "                ans.append(1)\n",
    "                carry = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) -1 , len(arr2) - 1\n",
    "\n",
    "        c = 0\n",
    "        ans = []\n",
    "\n",
    "        while i >= 0 or j >= 0 or c:\n",
    "            x = c\n",
    "            if i >= 0:\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "            \n",
    "            if x >= 2:\n",
    "                ans.append(x - 2)\n",
    "                c = -1\n",
    "            elif x >= 0:\n",
    "                ans.append(x)\n",
    "                c = 0\n",
    "            else:\n",
    "                ans.append(1)\n",
    "                c = 1\n",
    "            \n",
    "            i, j = i-1, j-1\n",
    "        \n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        intres = 0\n",
    "        arr1 = arr1[::-1]\n",
    "        arr2 = arr2[::-1]\n",
    "        for i in range(len(arr1)):\n",
    "            if (arr1[i] == 1):\n",
    "                intres += (-2)**i\n",
    "        # print (intres)\n",
    "        for i in range(len(arr2)):\n",
    "            if (arr2[i] == 1):\n",
    "                intres += (-2)**i\n",
    "        # print (intres)\n",
    "\n",
    "        if (intres == 0):\n",
    "            return [0]\n",
    "\n",
    "        if (intres == 1):\n",
    "            return [1]\n",
    "\n",
    "        # print (intres)\n",
    "        res = []\n",
    "        while (intres != 0):\n",
    "            r = intres % 2\n",
    "            if (r == 0):\n",
    "                res = [0] + res\n",
    "                intres = intres // (-2)\n",
    "            else:\n",
    "                res = [1] + res\n",
    "                intres = intres // (-2) + 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        :type arr1: List[int]\n",
    "        :type arr2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        a = self.negabinary_to_dec(arr1)\n",
    "        b = self.negabinary_to_dec(arr2)\n",
    "        return self.dec_to_negabinary(a+b)\n",
    "    \n",
    "    def negabinary_to_dec(self,arr):\n",
    "        s = 0\n",
    "        d = 1\n",
    "        i = len(arr)-1\n",
    "        while i>=0:\n",
    "            s += arr[i]*d\n",
    "            i -= 1\n",
    "            d *= -2\n",
    "        return s\n",
    "    \n",
    "    def dec_to_negabinary(self,n):\n",
    "        if n==0: return [0]\n",
    "        ret = []\n",
    "        while n != 0:\n",
    "            a = abs(n%(-2))\n",
    "            ret.append(a)\n",
    "            n = (n-a)//(-2)\n",
    "        return ret[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        arr1 = arr1[::-1]\n",
    "        arr2 = arr2[::-1]\n",
    "        c = 0\n",
    "        le1 = len(arr1)\n",
    "        le2 = len(arr2)\n",
    "        le = min(le1, le2)\n",
    "        ans = []\n",
    "        for i in range(le):\n",
    "            s = arr1[i] + arr2[i] + c\n",
    "            if s == -1:\n",
    "                c = 1\n",
    "                s = 1\n",
    "            else:\n",
    "                c = - (s >> 1)\n",
    "                s &= 1\n",
    "            ans.append(s)\n",
    "        for i in range(le, le1):\n",
    "            s = arr1[i] + c\n",
    "            if s == -1:\n",
    "                c = 1\n",
    "                s = 1\n",
    "            else:\n",
    "                c = - (s >> 1)\n",
    "                s &= 1\n",
    "            ans.append(s)\n",
    "        for i in range(le, le2):\n",
    "            s = arr2[i] + c\n",
    "            if s == -1:\n",
    "                c = 1\n",
    "                s = 1\n",
    "            else:\n",
    "                c = - (s >> 1)\n",
    "                s &= 1\n",
    "            ans.append(s)\n",
    "        if c == -1:\n",
    "            ans.append(1)\n",
    "            ans.append(1)\n",
    "        elif c == 1:\n",
    "            ans.append(1)\n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        a = len(arr1)\n",
    "        while arr1 and arr2:\n",
    "            res.append(arr1.pop()+arr2.pop())\n",
    "        res += arr1[::-1] + arr2[::-1] + [0 for i in range(a)]+[0,0]\n",
    "        l = len(res)\n",
    "        for i in range(l-2):\n",
    "            if res[i]>1:\n",
    "                res[i]-=2\n",
    "                res[i+1]-=1\n",
    "            elif res[i] == -1:\n",
    "                res[i]=1\n",
    "                res[i+1]+=1\n",
    "        for i in range(l):\n",
    "            if res[-1] == 0 and res != [0]:res.pop()\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        carry = 0\n",
    "        result = []\n",
    "        for i in range(max(len(arr1), len(arr2)) + 2):\n",
    "            sum = 0\n",
    "            if i < len(arr1): sum += arr1[-i-1]\n",
    "            if i < len(arr2): sum += arr2[-i-1]\n",
    "            sum += carry\n",
    "            print(sum)\n",
    "            if sum == 0 or sum == 1: \n",
    "                carry = 0\n",
    "                result.append(sum)\n",
    "            elif sum == 2 or sum == 3: \n",
    "                result.append(sum - 2)\n",
    "                carry = -1\n",
    "            elif sum == -1: \n",
    "                result.append(1)\n",
    "                carry = 1\n",
    "        while len(result) > 1:\n",
    "            if result[-1] == 0:\n",
    "                result.pop()\n",
    "            else:\n",
    "                break\n",
    "        return result[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        i, j = len(arr1) - 1, len(arr2) - 1\n",
    "        carry = 0\n",
    "        ans = list()\n",
    "\n",
    "        while i >= 0 or j >= 0 or carry:\n",
    "            x = carry\n",
    "            if i >= 0:\n",
    "\n",
    "                x += arr1[i]\n",
    "            if j >= 0:\n",
    "                x += arr2[j]\n",
    "\n",
    "            if x >= 2:\n",
    "                ans.append(x - 2)\n",
    "                carry = -1\n",
    "            elif x >= 0:\n",
    "                ans.append(x)\n",
    "                carry = 0\n",
    "            else:\n",
    "                ans.append(1)\n",
    "                carry = 1\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        \n",
    "        while len(ans) > 1 and ans[-1] == 0:\n",
    "            ans.pop()\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:\n",
    "        a = max(len(arr1), len(arr2)) + 2\n",
    "        arr = [0] * a\n",
    "        arr1, arr2 = arr1[::-1], arr2[::-1]\n",
    "        arr1.extend([0] * (a - len(arr1)))\n",
    "        arr2.extend([0] * (a - len(arr2)))\n",
    "        for i in range(a - 2):\n",
    "            if (arr[i] + arr1[i] + arr2[i] == 2 or arr[i] + arr1[i] + arr2[i] ==3) and (arr1[i+1]+arr2[i+1]==1 or arr1[i+1]+arr2[i+1]==2):\n",
    "                arr[i] =arr[i] + arr1[i] + arr2[i]-2\n",
    "                arr[i + 1] -= 1\n",
    "            elif (arr[i] + arr1[i] + arr2[i] == 2 or arr[i] + arr1[i] + arr2[i] ==3) and arr1[i+1]+arr2[i+1]==0:\n",
    "                arr[i]=arr[i] + arr1[i] + arr2[i]-2\n",
    "                arr[i+1]+=1\n",
    "                arr[i+2]+=1\n",
    "            else:\n",
    "                arr[i]=arr[i] + arr1[i] + arr2[i]\n",
    "        if arr[-1]!=0:\n",
    "            return arr[::-1]\n",
    "        if sum(arr)==0:\n",
    "            return [0]\n",
    "        i=a-2\n",
    "        while (arr[i]==0):\n",
    "            i-=1\n",
    "\n",
    "        return arr[:i+1][::-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
